package com.Questions.tanxin;


/**
 * 跳跃游戏
 */
public class leetcode45 {
    // 从距离终点最远的位置上开始寻找 能后跳到终点的起点
    // 再次寻找能跳到 该起点的最远位置
    // 反向查找出发的位置 由此作为贪心策略
    public int jump1(int[] nums) {
        int position=nums.length-1;
        int steps=0;
        while (position>0){
            for(int i=0;i<position;++i){
                if(i+nums[i]>=position){
                    position=i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }

    //方法二 正向查找可达的最大位置

    public int jump(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0;// 最远能到达的位置
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {// i 到达了能到达的最远距离
                end = maxPosition;// 更新最远距离
                steps++;// 步数增加
            }
        }
        return steps;
    }
}
